#include<iostream>
#include<cstring>
#define MAXSIZE 11

using namespace std;

typedef char ElemType[8];
typedef struct{
	ElemType data;
	int cur;
}NodeType;

NodeType space[MAXSIZE];

typedef struct {
	int elem;
	int length;
	int listSize;
}SLinkList;

void InitSpace_SL(){
	memset(space, 0 ,sizeof(space));
	for(int i=0;i<MAXSIZE-1;i++){
		space[i].cur=i+1;
	}
	space[MAXSIZE-1].cur=0;
}
int LocalElem_SL(SLinkList &S,ElemType e){
	int i = S.elem;
	while(i&&strcmp(space[i].data,e)){
		i = space[i].cur;
	}
	return i;
}
int Malloc_SL(){
	int i=space[0].cur;
	if(space[0].cur){
		space[0].cur=space[space[0].cur].cur;
	}
	return i;
}
void Free_SL(int k){
	space[k].cur=space[0].cur;
	space[0].cur=k;
}
void Print(){
	for(int i=0;i<MAXSIZE;i++){
		printf("%-8s%2d\n",space[i].data,space[i].cur);
	}
	printf("********************\n");
}
void CreateList_SL(SLinkList &S){
	S.elem=Malloc_SL();
	space[S.elem].cur=0;
	S.length=0;
	S.listSize=9;
}
void Insert_SL(SLinkList &S,int i,ElemType e){
	int cur=S.elem;
	int j=0;
	while(j<i-1){
		cur=space[cur].cur;
		j++;
	}
	int new_index=Malloc_SL();
	strcpy(space[new_index].data,e);
	space[new_index].cur=space[cur].cur;
	space[cur].cur=new_index;
	S.length++;
}
void Delete_SL(SLinkList &S,int i){
	int cur=S.elem;
	int j=0;
	while(j<i-1){
		cur=space[cur].cur;
		j++;
	}
	int delCur=space[cur].cur;
	space[cur].cur=space[delCur].cur;
	Free_SL(delCur);
	S.length--;
}

int main(){
	SLinkList S;
	InitSpace_SL();
	CreateList_SL(S);
	int a;
	ElemType e;
	char str[10];
	while(~scanf("%s",str)){
		if(strcmp(str,"insert")==0){
			scanf("%d%s",&a,e);
			Insert_SL(S,a,e);
		}else if(strcmp(str,"delete")==0){
			scanf("%d",&a);
			Delete_SL(S,a);
		}else if(strcmp(str,"search")==0){
			scanf("%s",e);
			printf("%2d\n********************\n",LocalElem_SL(S,e));
		}else if(strcmp(str,"show")==0){
			Print();
		}
	}
	return 0;
}
